Classes

Class notes and slides will be posted here.

Class 1: Theory and Practice (abhi shelat) [Slides: PDF]

Class 2: Modeling Computers [Slides: PDF, PPT]

Class 3: Deterministic Finite Automata [Notes: PDF]

Class 4: Nondeterministic Finite Automata [Notes: PDF]

Class 5: Pumping Lemma [Notes: PDF]

Class 6: Deterministic Pushdown Automata [Notes: PDF]

Class 7: Nondeterministic Pushdown Automata [Notes: PDF]

Class 8: Context-Free Languages [Slides: PDF]

Class 9: Context-Free Languages and proving non-context freeness [Notes: PDF]: Pumping lemma for CFLs

Class 10: Context-Free Languages Contextually [Slides: PDF, PPT]: DPDAs vs. NDPDAs, closure properties of CFLs

Class 11: Parsimonious Parsing [Slides: PDF, PPT]: Language classes, English, Parsing, LL(k)

Class 12: Indexed Grammars (Pieter Hooimeijer) [Slides: PDF]

Class 13: Turing Machines [Slides: PDF, PPT]: 2-Stack PDAs, Formal Notation for Turing Machines, Computing Model for Turing Machines

Class 14: Church-Turing Thesis [Slides: PPT, PDF]: TM computing model; deciders and recognizers; robustness of TM model

Class 15: Turing Machine Robustness (Qi Mi) [Slides: PPT, PDF]: Turing Machine variations, non-deterministic Turing Machines

Class 16: Universality and Undecidability [Slides: PPT, PDF]

Class 17: Proving Undecidability [Slides: PPT, PDF]: Reduction Proofs, Rice's Theorem

Class 18: Important Undecidable Problems [Slides: PPT, PDF]: Universal Programming Languages, Virus and Vulnerability Detection

Class 19: Undecidability in Theory and Practice [Slides: PPT, PDF]: PS5, Ali G, Busy Beavers

Class 20: Lambda Calculus and Computability (Yan Huang) [Slides: PPT, PDF; Notes]

Class 21: Introducing Complexity [Slides: PPT, PDF]: Exam 2, Computability and Complexity, Complexity Classes, Asymptotic Notation

Class 22: Classy Complexity Classes [Slides: PPT, PDF]: Non-Robustness of TM Model, Class P

Class 23: NP-Completeness (Isabelle Stanton) [Slides: PPT, PDF]

Class 24: P = NP ? [Slides: PPT, PDF]

Class 25: Security through Complexity? (Karsten Nohl) [Slides: PPT, PDF]

Class 26: Computing Genomes, Genomes Computing [Slides: PPT, PDF]